1. Field of the Invention
The invention relates to a method of and apparatus for determining a minimal length route between two nodes of a network comprising a plurality of nodes and links between the nodes.
2. Description of the Related Art
There are many applications of such a method and apparatus, one of which is the determination of the shortest route between two places on a map. Maps are now available in the form of digital data, as well as printed on paper, and a number of proposals have been made for using these to automatically generate the "best" route between two locations. Thus, the user enters the start and end places for a proposed journey, and the apparatus computes the "best" route. The term "best" here will depend on criteria which may be entered by the user. For example, whether the use of motorways or toll roads is or is not to be allowed, whether the shortest distance route is desired or the quickest route, whether the route should include a particular place or avoid such a place, etc.
When computing the route, the time taken to complete the computation is approximately proportional to the square of the number of nodes. As a result, while it is desirable to minimize the number of nodes, this reduces the number of places which can be defined. One solution to this problem is to form a hierarchical network with a top level having a limited number of nodes, and a lower level having further nodes which are attached to a particular node in the top level. A plurality of the lower level nodes may be attached to a single top level node. In this way, the top level nodes are used for the main routing calculation, with the attached lower level nodes being used to complete the route at one or both ends. It has been found that such an arrangement can lead to less than optimal routes being generated at each end of the journey as it requires a route through the high level node to which the lower level node is attached whether or not this is the most effective route and, in some cases, this can produce a route which instructs the traveller to pass through the intended destination to the high level node and then return to the intended destination.